Math
Note: If you cannot view some of the math on this page, you may need to add MathML support to your browser. If you have Mozilla/Firefox, go here and install the fonts. If you have Internet Explorer, go here and install the MathPlayer plugin.
Math
> Functions
> Hypotheses
Hypotheses
Hypotheses and theorems related to functions.Sibling topics:
Contents:
- Domain/codomain cardinality given a bijective function
- Empty codomain implies empty domain
- Empty domain implies empty function and image set
- Number of distinct bijective functions for a finite domain and codomain
- Number of distinct functions for a finite domain and codomain
- Number of distinct injective functions for a finite domain and codomain
- Number of distinct surjective functions for a finite domain and codomain
- Surjectivity does not imply injectivity and vice versa in infinite, equal domains and codomains
- Surjectivity implies injectivity and vice versa for finite, equal domains and codomains
Hypothesis: Domain/codomain cardinality given a bijective function
If there exists a bijective function from `A` to `B`, then `|A|=|B|`.
Hypothesis: Surjectivity implies injectivity and vice versa for finite, equal domains and codomains
Given `f:A->B` where `A=B` and `A` and `B` are finite, any surjective or
injective function must be bijective.
Corollary (of
Bijectivity in finite, equal domains/codomains):
Surjectivity does not imply injectivity and vice versa in infinite, equal domains and codomains
Given `f:A->A` where `A` is infinite, there exist functions that are injective but not
surjective and vice versa.
Theorem: Empty codomain implies empty domain
Given `f:A->B`, if `B=O/`, then `A=O/`.
Proof: Assume by way of contradiction that `B=O/` but `A!=O/`. Then there is an element `u in A`. By the
the definition of
a function, there exists an element `v in B` such that
`(u,v) in A xx B`. But `B=O/` so there can be no such element. Therefore, if `B=O/`, then `A=O/`.Theorem: Empty domain implies empty function and image set
Given `f:A->B`, if `A=O/`, then `f=O/ and Im(f)=O/`.
Proof: This theorem is really two theorems in one, so we'll address each separately.
- Assume by way of contradiction that `A=O/` but `f!=O/`. Then by the definition of a function, there is an element `(u,v) in A xx B`, but because `A=O/`, this cannot be the case. Therefore, if `A=O/`, then `B=O/`.
- Assume by way of contradiction that `A=O/` but `Im(f)!=O/`. Then, there exists an element `v` in the image set. By the definition of image set, there exists an element `u in A` such that `f(u)=v`. But since `A=O/`, that cannot be the case. Therefore, if `A=O/`, then `Im(f)=O/`.
Hypothesis: Number of distinct functions for a finite domain and codomain
The number of distinct functions from a finite domain `A` to a finite codomain `B` is given by
`|B|^|A|`. This is the number of distinct lists of length `|A|` that can formed using elements
from `B`.
Hypothesis: Number of distinct injective functions for a finite domain and codomain
The number of distinct injective functions from a finite domain `A` to a finite domain `B` is
given by `{(0,if |A|>|B|),((|B|!)/((|B|-|A|)!),otherwise):}}`. This is equal to the number of
permutations of `B` containing `|A|` elements.
Hypothesis: Number of distinct surjective functions for a finite domain and codomain
The number of distinct surjective functions from a finite domain `A` to a finite domain `B`
is given by `{(0,if |A|<|B|),(|B|^(|A|-|B|)xx|B|!,otherwise):}}`. This is equal to the number of
permutations of `B` times the number of unique lists of length `|A|-|B|`
that can be formed using elements from `B`.
Hypothesis: Number of distinct bijective functions for a finite domain and codomain
The number of distinct injective functions from a finite domain `A` to a finite domain `B` is
given by `{(0,if |A|!=|B|),(|B|!,otherwise):}}`. This is equal to the number of permutations of `B`.